{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "This code is used to recover the hidden number problem.\n",
    "Suppose that the modulus, alpha and the middle bits of beta are given, we need to recover the hidden number.\n",
    "The software used is the Sagemath.\n",
    "This code gives five methods: the \"continued fraction + lattice\" method, the lattice method for finding lambda, the lattice method given in inscrypt21, a new lattice-based method and an improved data-saving method.\n",
    "'''\n",
    "\n",
    "import time\n",
    "\n",
    "# Randomly divide m into n segments, the sum of the even segments is K\n",
    "def distribution(n, m, K):\n",
    "    d = vector(ZZ, n)\n",
    "    known = vector(ZZ, int((n - 1)/2))\n",
    "    unknown = vector(ZZ, int((n + 1)/2))\n",
    "    \n",
    "    known[0] = randint(1, K - 1)\n",
    "    known[len(known) - 1] = K\n",
    "    i = 1\n",
    "    while i < (n - 1)/2 - 1:\n",
    "        k = randint(1, K - 1)\n",
    "        jud = 0\n",
    "        flag = 0\n",
    "        for j in range(0, i):\n",
    "            if k == known[j]:\n",
    "                flag = 1\n",
    "                break\n",
    "            if k < known[j]:\n",
    "                for ii in range(j, i):\n",
    "                    known[i + j - ii] = known[i + j - ii - 1]\n",
    "                known[j] = k\n",
    "                break\n",
    "            if k > known[j]:\n",
    "                jud = jud + 1\n",
    "        if jud == i:\n",
    "            known[i] = k\n",
    "        if flag == 0:\n",
    "            i = i + 1\n",
    "            \n",
    "    unknown[0] = randint(1, m - K - 1)\n",
    "    unknown[len(unknown) - 1] = m - K\n",
    "    i = 1\n",
    "    while i < (n + 1)/2 - 1:\n",
    "        k = randint(1, m - K - 1)\n",
    "        jud = 0\n",
    "        flag = 0\n",
    "        for j in range(0, i):\n",
    "            if k == unknown[j]:\n",
    "                flag = 1\n",
    "                break\n",
    "            if k < unknown[j]:\n",
    "                for ii in range(j, i):\n",
    "                    unknown[i + j - ii] = unknown[i + j - ii - 1]\n",
    "                unknown[j] = k\n",
    "                break\n",
    "            if k > unknown[j]:\n",
    "                jud = jud + 1\n",
    "        if jud == i:\n",
    "            unknown[i] = k\n",
    "        if flag == 0:\n",
    "            i = i + 1\n",
    "      \n",
    "    d[0] = unknown[0]\n",
    "    d[1] = known[0]\n",
    "    for i in range(1, len(unknown)):\n",
    "        d[2 * i] = unknown[i] - unknown[i - 1]\n",
    "    for i in range(1, len(known)):\n",
    "        d[2 * i + 1] = known[i] - known[i - 1]\n",
    "        \n",
    "    return d\n",
    "\n",
    "# The \"continued fraction + lattice\" method\n",
    "def continued_fractions_method(n, q, A, R, d):\n",
    "    m = ceil(q.log() / 2.log())\n",
    "    a = 2^(d[0] + d[1])\n",
    "    b = q / 2^(d[0] + d[1] / 2)\n",
    "    PQ = convergents(a/q)\n",
    "    for i in range(0, len(PQ) - 1):\n",
    "        if PQ[i].denominator() < RDF(b) and RDF(b) <= PQ[i + 1].denominator():\n",
    "            lamda = PQ[i].denominator()\n",
    "            break\n",
    "    \n",
    "    L = Matrix(ZZ, n + 2, n + 2)\n",
    "    x = vector(ZZ, n + 2)\n",
    "    for i in range(0, n):\n",
    "        L[i, i] = q * 2^(ceil(d[1] / 2) - 1)\n",
    "        L[n, i] = ((lamda * A[0, i]) % q) * 2^(ceil(d[1] / 2) - 1)\n",
    "        L[n + 1, i] = ((lamda * R[0, i] * 2^d[0]) % q) * 2^(ceil(d[1] / 2) - 1)\n",
    "    L[n, n] = 1\n",
    "    L[n + 1, n + 1] = 2^(ceil(d[1] / 2) - 1)\n",
    "    \n",
    "    reduced_L = L.BKZ(block_size = 20)\n",
    "    \n",
    "    j = 0\n",
    "    for i in range(0, n + 2):\n",
    "        if reduced_L[i, n + 1].abs() == L[n + 1, n + 1]:\n",
    "            x[j] = reduced_L[i, n].abs()\n",
    "            j = j + 1\n",
    "    \n",
    "    return x\n",
    "\n",
    "# The lattice method for finding lambda\n",
    "def balanced_lattice_method(n, q, A, R, d):\n",
    "    l = len(d)\n",
    "    m = 256\n",
    "    L = Matrix(ZZ, (l + 1) / 2, (l + 1) / 2)\n",
    "    for i in range(0, (l - 1) / 2):\n",
    "        L[i, i] = q * 2^(d[2 * (i + 1)])\n",
    "        L[(l - 1) / 2, i] = 1\n",
    "        for j in range(0, 2 * (i + 1) + 1):\n",
    "            L[(l - 1) / 2, i] = L[(l - 1) / 2, i] * 2^(d[j])\n",
    "    L[(l - 1) / 2, (l - 1) / 2] = 2^d[0]\n",
    "    \n",
    "    reduced_L = L.BKZ(block_size = 20)\n",
    "    \n",
    "    sum_unknown = 0\n",
    "    for i in range(0, (l + 1) / 2):\n",
    "        sum_unknown = sum_unknown + reduced_L[0, i].abs()\n",
    "    len_unknown = ceil(sum_unknown.log()/2.log())\n",
    "    lamda = reduced_L[0, (l - 1) / 2].abs() / 2^d[0]\n",
    "        \n",
    "    LL = Matrix(ZZ, n + 2, n + 2)\n",
    "    x = vector(ZZ, n + 2)\n",
    "    for i in range(0, n):\n",
    "        LL[i, i] = q * 2^(m - len_unknown)\n",
    "        LL[n, i] = ((lamda * A[0, i]) % q) * 2^(m - len_unknown)\n",
    "        LL[n + 1, i] = 0\n",
    "        for j in range(0, (l - 1) / 2):\n",
    "            known = 0\n",
    "            for k in range(0, 2 * j + 1):\n",
    "                known = known + d[k]     \n",
    "            LL[n + 1, i] = LL[n + 1, i] + 2^known * R[j, i]\n",
    "        LL[n + 1, i] = ((lamda * LL[n + 1, i] + 2^(len_unknown - 1)) % q) * 2^(m - len_unknown)      \n",
    "    LL[n, n] = 1\n",
    "    LL[n + 1, n] = 2^(len_unknown - 1) * 2^(m - len_unknown)\n",
    "    LL[n + 1, n + 1] = 2^(len_unknown - 1) * 2^(m - len_unknown)\n",
    "    \n",
    "    reduced_LL = LL.BKZ(block_size = 20)\n",
    "    \n",
    "    j = 0\n",
    "    for i in range(0, n + 2):\n",
    "        if reduced_LL[i, n + 1] == -LL[n + 1, n + 1]:\n",
    "            x[j] = LL[n + 1, n] + reduced_LL[i, n]\n",
    "            j = j + 1\n",
    "        if reduced_LL[i, n + 1] == LL[n + 1, n + 1]:\n",
    "            x[j] = LL[n + 1, n] - reduced_LL[i, n]\n",
    "            j = j + 1\n",
    "    \n",
    "    return x\n",
    "\n",
    "# The lattice method given in inscrypt21\n",
    "def lattice21_method(n, q, A, R, d):\n",
    "    L = Matrix(ZZ, 2 * n + 1, 2 * n + 1)\n",
    "    a_inv = (A[0, 0]^(-1)) % q\n",
    "    for i in range(0, n - 1):\n",
    "        L[i, i] = q\n",
    "        L[n - 1, i] = (A[0, i + 1] * a_inv) % q\n",
    "        L[n, i] = (A[0, i + 1] * a_inv * 2^(d[0] + d[1])) % q\n",
    "        L[n + 1 + i, i] = 2^(d[0] + d[1])\n",
    "        L[2 * n, i] = ((R[0, i + 1] * 2^d[0] - A[0, i + 1] * a_inv * 2^d[0] * R[0, 0]) % q) + 2^(d[0] - 1)\n",
    "    \n",
    "    L[n - 1, n - 1] = 1\n",
    "    L[2 * n, n - 1] = 2^(d[0] - 1)\n",
    "    L[2 * n, n] = 2^(d[0] - 1)\n",
    "    L[2 * n, 2 * n] = 2^(d[0] - 1)\n",
    "    for i in range(n + 1, 2 * n):\n",
    "        L[2 * n, i] = -2^(d[0] - 1)\n",
    "    if d[0] >= d[2]:\n",
    "        for i in range(n, 2 * n):\n",
    "            L[i, i] = 2^(d[0] - d[2])\n",
    "    else:\n",
    "        for i in range(0, 2 * n + 1):\n",
    "            for j in range(0, 2 * n + 1):\n",
    "                L[i, j] = L[i, j] * 2^(d[2] - d[0])\n",
    "        for i in range(n, 2 * n):\n",
    "            L[i, i] = 1\n",
    "\n",
    "    reduced_L = L.BKZ(block_size = 20)\n",
    "    x = vector(ZZ, 2 * n + 1)\n",
    "    j = 0\n",
    "    for i in range(0, 2 * n + 1):\n",
    "        if reduced_L[i, 2 * n] == -L[2 * n, 2 * n]:\n",
    "            b1 = (L[2 * n, n - 1] + reduced_L[i, n - 1]) / L[n - 1, n - 1]\n",
    "            b3 = (L[2 * n, n] + reduced_L[i, n]) / L[n, n]\n",
    "            b = b1 + R[0, 0] * 2^d[0] + b3 * 2^(d[0] + d[1])\n",
    "            x[j] = (a_inv * b) % q\n",
    "            j = j + 1\n",
    "        if reduced_L[i, 2 * n] == L[2 * n, 2 * n]:\n",
    "            b1 = (L[2 * n, n - 1] - reduced_L[i, n - 1]) / L[n - 1, n - 1]\n",
    "            b3 = (L[2 * n, n] - reduced_L[i, n]) / L[n, n]\n",
    "            b = b1 + R[0, 0] * 2^d[0] + b3 * 2^(d[0] + d[1])\n",
    "            x[j] = (a_inv * b) % q\n",
    "            j = j + 1\n",
    "    \n",
    "    return x\n",
    "\n",
    "# Our new lattice-based method\n",
    "def new_lattice_method(n, q, A, R, d):\n",
    "    m = 256\n",
    "    L = Matrix(ZZ, 2 * n + 2, 2 * n + 2)\n",
    "    for i in range(0, n):\n",
    "        L[i, i] = q * 2^(m - d[0])\n",
    "        L[n, i] = A[0, i] * 2^(m - d[0])\n",
    "        L[n + 1, i] = R[0, i] * 2^m + 2^(m - 1)\n",
    "    L[n, n] = 1\n",
    "    L[n + 1, n] = 2^(m - 1)\n",
    "    L[n + 1, n + 1] = 2^(m - 1)\n",
    "    for i in range(n + 2, 2 * n + 2):\n",
    "        L[n + 1, i] = -2^(m - 1)\n",
    "    for i in range(n + 2, 2 * n + 2):\n",
    "        L[i, i - n - 2] = 2^(m + d[1])\n",
    "        L[i, i] = 2^(m - d[2])\n",
    "\n",
    "    reduced_L = L.BKZ(block_size = 20)\n",
    "    \n",
    "    x = vector(ZZ, 2 * n + 2)\n",
    "    j = 0\n",
    "    for i in range(0, 2 * n + 2):\n",
    "        if reduced_L[i, n + 1] == -L[n + 1, n + 1]:\n",
    "            x[j] = L[n + 1, n] + reduced_L[i, n]\n",
    "            j = j + 1\n",
    "        if reduced_L[i, n + 1] == L[n + 1, n + 1]:\n",
    "            x[j] = L[n + 1, n] - reduced_L[i, n]\n",
    "            j = j + 1\n",
    "    \n",
    "    return x\n",
    "\n",
    "# An improved data-saving method\n",
    "def improved_lattice_method(n, q, A, R, d, gamma, X):\n",
    "    m = 256\n",
    "    L = Matrix(ZZ, 2 * n + 2, 2 * n + 2)\n",
    "    for i in range(0, n):\n",
    "        L[i, i] = q * 2^(m - d[0] - gamma)\n",
    "        L[n, i] = A[0, i] * 2^(m - d[0] - gamma)\n",
    "        L[n + 1, i] = R[0, i] * 2^(m - gamma) + 2^(m - gamma - 1)\n",
    "    L[n, n] = 1\n",
    "    L[n + 1, n] = 2^(m - gamma) * (X >> (m - gamma)) + 2^(m - gamma - 1)\n",
    "    L[n + 1, n + 1] = 2^(m - gamma - 1)\n",
    "    for i in range(n + 2, 2 * n + 2):\n",
    "        L[n + 1, i] = -2^(m - gamma - 1)\n",
    "    for i in range(n + 2, 2 * n + 2):\n",
    "        L[i, i - n - 2] = 2^(m + d[1] - gamma)\n",
    "        L[i, i] = 2^(m - d[2] - gamma)\n",
    "\n",
    "    reduced_L = L.BKZ(block_size = 20)\n",
    "    \n",
    "    x = vector(ZZ, 2 * n + 2)\n",
    "    j = 0\n",
    "    for i in range(0, 2 * n + 2):\n",
    "        if reduced_L[i, n + 1] == -L[n + 1, n + 1]:\n",
    "            x[j] = L[n + 1, n] + reduced_L[i, n]\n",
    "            j = j + 1\n",
    "        if reduced_L[i, n + 1] == L[n + 1, n + 1]:\n",
    "            x[j] = L[n + 1, n] - reduced_L[i, n]\n",
    "            j = j + 1\n",
    "    \n",
    "    return x\n",
    "\n",
    "# Check whether x is the hidden number \n",
    "def judgement_x(X, x):\n",
    "    jud = 0\n",
    "    for i in range(0, len(x)):\n",
    "        if X == x[i]:\n",
    "            jud = 1\n",
    "            break\n",
    "            \n",
    "    return jud\n",
    "              \n",
    "\n",
    "m = 256\n",
    "q = 115792089237316195423570985008687907853269984665640564039457584007913129639747\n",
    "K = 8    # The number of unknown bits\n",
    "N = 500\n",
    "gamma = 6\n",
    "Tn = 40\n",
    "start = time.time()\n",
    "for n_i in range(0, Tn):\n",
    "    n = Tn - n_i\n",
    "    print(n)\n",
    "    success_x = vector(ZZ, 5)\n",
    "    for count in range(0, 10):\n",
    "        A = random_matrix(ZZ, 1, N, x = 0, y = q)\n",
    "        X = randint(0, q - 1)\n",
    "        R = Matrix(ZZ, 1, N)\n",
    "        d = distribution(3, m, K)\n",
    "        for i in range(0, N):\n",
    "            R[0, i] = (((A[0, i] * X) % q) >> d[0]) % (2^d[1])\n",
    "\n",
    "        x1 = continued_fractions_method(n, q, A, R, d)\n",
    "        jx1 = judgement_x(X, x1)\n",
    "        success_x[0] = success_x[0] + jx1\n",
    "\n",
    "        x2 = balanced_lattice_method(n, q, A, R, d)\n",
    "        jx2 = judgement_x(X, x2)\n",
    "        success_x[1] = success_x[1] + jx2\n",
    "        \n",
    "        x3 = lattice21_method(n, q, A, R, d)\n",
    "        jx3 = judgement_x(X, x3)\n",
    "        success_x[2] = success_x[2] + jx3\n",
    "\n",
    "        x4 = new_lattice_method(n, q, A, R, d)\n",
    "        jx4 = judgement_x(X, x4)\n",
    "        success_x[3] = success_x[3] + jx4\n",
    "\n",
    "        x5 = improved_lattice_method(n, q, A, R, d, gamma, X)\n",
    "        jx5 = judgement_x(X, x5)\n",
    "        success_x[4] = success_x[4] + jx5\n",
    "    print(success_x,'\\n')\n",
    "end = time.time()\n",
    "print('time:',end-start,'s')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.1",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
